package com.pandy.code;

import java.util.Stack;

/**
 * @description: 单向链表练习题：是否为回文结构
 * @author: panhong
 * @date: 2025/3/26
 */
public class Code10_List_Palindrome {

    static class Node {
        int value;
        Code10_List_Palindrome.Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 判断是否为回文结构
     * 使用容器实现
     * @param head
     * @return
     */
    public static boolean palindrome1(Code10_List_Palindrome.Node head) {
        if(head == null) {
            return false;
        }

        Stack<Code10_List_Palindrome.Node> stack = new Stack<>();
        Code10_List_Palindrome.Node node = head;
        while (node != null) {
            stack.push(node);
            node = node.next;
        }

        while (head != null) {
            if(head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }


    /**
     * 判断是否为回文结构
     * 不使用容器实现
     * @param head
     * @return
     */
    public static boolean palindrome2(Code10_List_Palindrome.Node head) {
        if(head == null || head.next == null) {
            return true;
        }

        // 1. 先找链表中点
        Node f = head.next;
        Node s = head.next;
        while (f.next != null && f.next.next != null) {
            f = f.next.next;
            s = s.next;
        }

        // s 节点即为中点

        // 2.中点后半段逆序
        Node n1 = s.next;
        s.next = null;
        Node n = null;
        while (n1 != null) {
            n = n1.next;
            n1.next = s;
            s = n1;
            n1 = n;
        }


        // 3.两个指针 L R
        // head是L指针 n可以是R指针
        Node l = head;
        Node r = s; // s节点是最后一个节点
        boolean isPalindrome = true;
        while (l != null && r != null) {
            if(l.value != r.value) {
                isPalindrome = false;
                break;
            }
            l = l.next;
            r = r.next;
        }

        // 4.还原链表 从最后一个节点还原  （特别重要，上面不能只能返回了，需要将链表结构还原）
        n1 = s.next;
        s.next = null;
        while (n1 != null) {
            s = n1.next;
            n1.next = n;
            n = n1;
            n1 = s;

        }

        return isPalindrome;
    }


    public static void main(String[] args) {
        Code10_List_Palindrome.Node node1 = new Code10_List_Palindrome.Node(1);
        Code10_List_Palindrome.Node node2 = new Code10_List_Palindrome.Node(2);
        Code10_List_Palindrome.Node node3 = new Code10_List_Palindrome.Node(3);
        Code10_List_Palindrome.Node node4 = new Code10_List_Palindrome.Node(1);
        Code10_List_Palindrome.Node node5 = new Code10_List_Palindrome.Node(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        System.out.println(palindrome2(node1));
    }
}
